1. Field of the Invention
The present invention relates to a method and device for generating redundant code based on data, a method and device for using the redundant code to restore original data, and a RAID (Redundant Array of Inexpensive Disks, or Redundant Array of Independent Disks) storage device that uses the redundant code.
2. Description of the Related Art
One technique for detecting various errors that can occur in data and correcting these errors involves generating redundant code based on data and adding this redundant code to the data. When redundant code is used to improve fault tolerance, data are used as is when errors do not occur in data, but when an error such as block loss occurs in the data, the redundant code is used to restore or recover the original data. Such redundant code is used in, for example, a RAID system.
A RAID system is a storage device configured by connecting a plurality of disk drives as a disk array, and to raise the reliability and speed of reading/writing, while conferring redundancy, records data that are both distributed and redundant on a plurality of disk drives. In a RAID system, fault tolerance is improved regarding the failure of disk drives, and data can be correctly read even when, for example, a failure occurs in one disk drive. RAID systems are classified into several types depending on the redundancy configuration, but of these types, as shown in James S. Plank, “A Tutorial on Reed-Solomon Coding for Fault-tolerance in RAID-like Systems,” Technical Report UT-CS-96-332, University of Tennessee, July 1996 [1]; and James S. Plank and Ying Ding, “Note: Correction to the 1997 Tutorial on Reed-Solomon Coding,” Technical Report UT-CS-03-504, University of Tennessee, April 2003 [2], the RAID 6 System, when dividing data into blocks and distributing and arranging the blocks in a plurality of disk drives, calculates Reed-Solomon code from the blocks and then stores this Reed-Solomon code in the disk drives together with the data that are divided into blocks. Reed-Solomon code is redundant code that uses an operation in a Galois field (i.e., finite field). To state in detail, a RAID 6 system uses a minimum of six disk drives, generates two types of parity codes (redundant codes) called P and Q, stores P-code data strings in one disk drive, stores Q-code data strings in another disk drive, and distributes and stores data in the remaining disks, and can thereby cope with failures in up to two disk drives of the whole.
Redundant code that employs a Galois field operation is known for its superior redundancy. Nevertheless, a Galois field operation represents a large processing burden for a general-purpose microprocessor or CPU (Central Processing Unit) and requires lengthy computation time. FIG. 1 is a view for describing the process of calculating redundant code, which is a Reed-Solomon code, in the related art of the present invention, and shows a process of generating redundant code strings P and Q from a bit string using a 24-extended Galois field (GF(24)). Here, the data that are the object of the redundant code string generation are divided into the four bit strings a, b, c, and d. Bit string a is composed of bits a00, a01 a02, a03, . . . and bit string b is composed of bits b00, b01, b02, b03, . . . . Bit strings c and d are similar. In addition, redundant code strings P and Q are also both bit strings, redundant code string P being composed of bits P00, P01, P02, P03, and redundant code string Q is composed of bits Q00, Q01, Q02, Q03, . . . .
Here, through the use of extended Galois field GF(24), the computation of the redundant code strings is carried out by extracting four bits at a time from bit strings, and each of redundant code strings P and Q is also generated four bits at a time by a single computation shown in FIG. 1. In FIG. 1, I is a 4×4 identity matrix, and T is a companion matrix of the primitive polynomial (x4+x+1−0) of GF(24), and is the 4×4 matrix indicated by equation (1). In the figures and in the present specification, the explicit addition symbol (“+”) does not indicate normal addition, but rather, indicates exclusive OR (XOR or eXclusive OR, ExOR) operation.
                    T        =                              (                                                            0                                                  0                                                  0                                                  1                                                                              1                                                  0                                                  0                                                  1                                                                              0                                                  1                                                  0                                                  0                                                                              0                                                  0                                                  1                                                  0                                                      )                    .                                    (        1        )            For example, Q00 is calculated by:Q00=a00+b03+c00+c03+d02  (2).
Because this is an exclusive OR operation, Q00 is “1” if there is an odd number of bits having the value “1” among the five bits a00, b03, c00, c03, d02, the value of Q00 otherwise being “0.”
Thus, an ordinary Galois field operation is carried out in bit units. Galois field operation is also implemented when using redundant code strings to restore original data.
However, a typical CPU or microprocessor executes operations in word units with, for example, eight bits (i.e., one byte), 16 bits, 32 bits or 64 bits as one word. Exclusive OR operations are also executed in the word units, and at such times, the exclusive OR is computed for corresponding bits between words that are the objects of computation. In other words, the result C of an exclusive OR operation for words A and B is also data of one word, the value of the exclusive OR of the first bit of word A and the first bit of word B being stored in the first bit of word C, and the result of the exclusive OR of the second bit of word A and the second bit of word B being stored in the second bit of word C.
When this type of CPU is used to execute the above-described Galois field operation, all of bit strings a to d can be treated as word data, but when computing, for example, redundant code string Q, the exclusive OR of bit a00 that is the first bit of bit string a and bit b03 that is the fourth bit of bit string b must be computed, as shown in equation (2). In other words, a bit shift operation must be carried out in the data. Still further, in an exclusive OR operation by word units, a mask operation of data in bit units must be carried out to prevent the operation result from being influenced by bits that are irrelevant to the operation at that point in time. The number of times this bit shift and data masking are executed is considerable. However, due to the architecture of a general-purpose CPU, bit shift instructions and data mask instructions cannot be efficiently executed, and these processes therefore place a heavy processing burden on the CPU.
When a general-purpose CPU is incorporated in a device, Galois field operations carried out by the CPU may affects the processing performance of the device. As a result, in the related art of the present invention, some type of hardware dedicated to Galois field operations for generating redundant code is considered essential to realize these operations at high speed. For example, JP-A-2007-129618 discloses an example in which a Galois field multiplying circuit necessary for Reed-Solomon decoding is made up from a hardware circuit composed of a large number of constituent elements.
For example, JP-A-2008-176621 discloses an example in which, to generate data to be stored in each disk drive in a RAID system, a general-purpose CPU is used to carry out a bit-shift operation, a data-mask operation, an AND operation, and an exclusive OR operation to carry out a Galois field multiplying operation. In addition, JP-A-2008-186400 discloses an example in which reference is made to a Galois field multiplication table to restore original data from data to which redundant code has been added by the method of JP-A-2008-176621.
Although there are cases in which Galois field operations are carried out using a general-purpose microprocessor or CPU as disclosed in JP-A-2008-176621 and JP-A-2008-186400, dedicated hardware capable of executing processes corresponding to bit shift at high speed must be employed when a Galois field operation is to be carried out at high speed. However, dedicated hardware for carrying out Galois field operations at high speed is costly, and a method is therefore sought that will enable Galois field operations to be executed at high speed using only a general-purpose CPU and without using special hardware.